R-Version: [Default] [32-bit] C:\Program Files\R\R-4.1.0

In folgendem Notebook werden anhand des MovieLense Datensatzes aus dem Paket RecommenderLab verschiedene Recommender erstellt. Es werden verschiedene Recommender und verschiedene Ähnlichkeiten verwendet, um diese zu vergleichen und auszuwerten. Ziel ist es, ein möglichst guter Recommender zu erstellen und zu verstehen wie dieser funktioniert. Zudem soll verstanden werden wie dieser bewertet wird und was in diesem Falle ein ‘guter’ Recommender bedeutet.

Dieses Notebook konzentriert sich auf Erkenntnisse von Auswertungen und Vergleichen. Um eine bessere Übersicht zu erhalten wurden grosse, sich widerholende Codes im Helperfile helper.R ausgelagert.

2.Binäre User-Liked-Items Matrix für alle Nutzer erzeugen.

movies_binary <- movies %>% mutate(rating = ifelse(rating > 3, 1, 0))
movies_wider <- pivot_wider(movies_binary, id_cols = user, names_from = item, values_from = rating)
rownames(movies_wider) <- movies_wider$user
Setting row names on a tibble is deprecated.
movies_wider['user'] <- NULL
user_movie_matrix <- as.matrix(movies_wider)
movies_wider

Für die Binäre User-Liked Matrix setzten wir die Grenze für ein gutes Rating bei >4. Also alle Filme, welche mit einem Rating von 3 oder weniger bewertet wurden, werden als schlecht bewertet definiert (also 0), wobei Filme mit Bewertungen von 4 oder 5 als gut bewertet definiert sind (1).

binary_non_na <- as(binarize(MovieLense, minRating = 4), 'matrix') * 1
binary_non_na[1:3, 1:3]
  Toy Story (1995) GoldenEye (1995) Four Rooms (1995)
1                1                0                 1
2                1                0                 0
3                0                0                 0

Um

3.Dimension der User-Liked-Items Matrix prüfen und ausgeben.

dim(user_movie_matrix)
[1]  943 1664

4.Movie-Genre Matrix für alle Filme erzeugen.

genres <- MovieLenseMeta
genres <- genres %>% select("title",'unknown':'Western')
rownames(genres) <- genres$title
genres['title'] <- NULL
movie_genre_matrix <- as.matrix(genres)
genres

5.Dimension der Movie-Genre Matrix prüfen und ausgeben.

dim(movie_genre_matrix)
[1] 1664   19
class(movie_genre_matrix)
[1] "matrix" "array" 
user_movie_matrix[1:3, 1:3]
     Toy Story (1995) GoldenEye (1995) Four Rooms (1995)
[1,]                1                0                 1
[2,]                1               NA                NA
[3,]               NA               NA                NA
class(user_movie_matrix)
[1] "matrix" "array" 

6.Anzahl unterschiedlicher Filmprofile bestimmen und visualisieren.

movie_genre_profile_matrix <- as.matrix(apply(movie_genre_matrix == 1, 1, 
                                       function(a) paste0(colnames(movie_genre_matrix)[a], collapse = "")))
movie_genre_profile_df <- as.data.frame(movie_genre_profile_matrix)
movie_genre_profile_df$items <- rownames(movie_genre_profile_df)

#movie_genre_profile_list <- c(unique(movie_genre_profile_df$V1))
#movie_genre_profile_list <- strsplit(movie_genre_profile_list, "\n")
#length(movie_genre_profile_list)

movie_genre_profile_df

TODO: igewie die einzelne genreprofil zelle, inen df speichere und plotte(grafik vode slides vom dani, glaub folie 13)

In dem MovieLense Datenset sind insgesamt 216 verschiedene Genreprofile von den Filmen vertreten. Das bedeitet, es sind 216 verschiedene Genrekombinationen aus den 16 gegebenen Genres entstanden. (r isch so en seich plötzlich bruuchsch nömm ‘as(data, ’data.frame)’ sondern ‘as.data.frame(data)’ WIESO????)

movie_genre_profile_df <- movie_genre_profile_df %>%
  group_by(V1)
movie_genre_profile_df
nr_diff_movies <- binary_non_na %*% movie_genre_matrix
nr_diff_movies <- as.data.frame(nr_diff_movies)

nr_diff_movies_mean <- rownames_to_column(nr_diff_movies)

nr_diff_movies_mean <- pivot_longer(nr_diff_movies_mean, cols = !rowname, names_to = 'genre', values_to = 'count')
nr_diff_movies_mean <- nr_diff_movies_mean %>% group_by(genre) %>% summarize(count = mean(count))

nr_diff_movies

TODO: Visualisierung der verschiedener Nutzerprofile ( siehe slide 13 Daniel) In dieser Matrix ist zu sehen wie viele Filme pro genre mit mehr als 3 bewertet wurden, jeweils pro User.

nr_diff_movies_mean
nr_diff_movies_mean %>% mutate(genre = fct_reorder(genre, count)) %>% 
  ggplot(aes(x = genre, y = count)) + 
  geom_col(fill = 'steelblue') +
  coord_flip() +
  scale_y_continuous(expand = c(0,0), limits = c(0, 30)) +
  geom_text(aes(label = round(count, 2)), hjust=-0.2, color = 'black') +
  labs(
    title = "Duchschnittliche Anzahl positiv bewerteter Filme pro Genre",
    x = element_blank(), 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

7.User-Genre-Profil Matrix mit Nutzerprofilen im Genre-Vektorraum erzeugen.

##8.Dimension der User-Genre-Profil Matrix prüfen und ausgeben.

9.Anzahl unterschiedlicher Nutzerprofile bestimmen, wenn Stärke der GenreKombination (a) vollständig bzw. (b) nur binär berücksichtigt wird.

Ähnlichkeit von Nutzern und Filmen

1.Cosinus-Ähnlichkeit zwischen User-Genre- und Movie-Genre-Matrix berechnen.

Test


A_test.data <- c(1.5,2.5, 1.,0.5)
A_test <- matrix(A_test.data, nrow=2)
A_test
     [,1] [,2]
[1,]  1.5  1.0
[2,]  2.5  0.5
B_test.data <- c(0.5,1., 1.5,2.)
B_test <- matrix(B_test.data, nrow=2)
B_test
     [,1] [,2]
[1,]  0.5  1.5
[2,]  1.0  2.0
result <- calc_cos_similarity_twomtrx(A_test, B_test)

if((dim(result) == dim(B_test)) && (dim(result) == dim(A_test))) {
  print("dimensions match")
} else {
  print("dimensions do not match")
}
[1] "dimensions match"
check.data <- c(0.79, 0.50, 0.87, 0.61)
check <- matrix(check.data, nrow=2)

if(max(abs(check - result)) < 1e-2){
  print("check match")
} else{
  print("check differs from result")
}
[1] "check match"

In diesem Beispiel wurde für zwei 2x2 Matrizen mit zufällig gewählten Werten die cosine similarity berechnet. Diese Berechnung wurde ebenfalls von Hand gemacht und mit der Implementierung abgegelichen. Zusätzlich wurden die Dimensionen der Inputvariablen mit deren des Resultates abgeglichen. Die Berechnung der Cosine Similarity sollte so korrekt sein.

Anschliessend wird die Cosine Similarity der user-genre und movie-genre Matrixberechnet.

user_movie_non_na <- user_movie_matrix
user_movie_non_na[is.na(user_movie_non_na)] <- 0
user_movie_non_na[1:5, 1:5]
     Toy Story (1995) GoldenEye (1995) Four Rooms (1995) Get Shorty (1995) Copycat (1995)
[1,]                1                0                 1                 0              0
[2,]                1                0                 0                 0              0
[3,]                0                0                 0                 0              0
[4,]                0                0                 0                 0              0
[5,]                1                0                 0                 0              0

similarity <- calc_cos_similarity_twomtrx(user_movie_non_na, t(movie_genre_matrix))
summary(similarity)
    unknown              Action          Adventure         Animation         Children's          Comedy       
 Min.   :0.0000000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000  
 1st Qu.:0.0000000   1st Qu.:0.05174   1st Qu.:0.02713   1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.03723  
 Median :0.0000000   Median :0.09530   Median :0.06691   Median :0.02291   Median :0.02440   Median :0.06872  
 Mean   :0.0005492   Mean   :0.11033   Mean   :0.07884   Mean   :0.03708   Mean   :0.03679   Mean   :0.08106  
 3rd Qu.:0.0000000   3rd Qu.:0.15322   3rd Qu.:0.11681   3rd Qu.:0.05657   3rd Qu.:0.05270   3rd Qu.:0.11617  
 Max.   :0.2236068   Max.   :0.39834   Max.   :0.37064   Max.   :0.29513   Max.   :0.31642   Max.   :0.36430  
 NA's   :1           NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1        
     Crime          Documentary           Drama            Fantasy          Film-Noir           Horror       
 Min.   :0.00000   Min.   :0.000000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000  
 1st Qu.:0.02890   1st Qu.:0.000000   1st Qu.:0.07013   1st Qu.:0.00000   1st Qu.:0.00000   1st Qu.:0.00000  
 Median :0.05600   Median :0.000000   Median :0.10636   Median :0.00000   Median :0.02182   Median :0.02198  
 Mean   :0.06107   Mean   :0.008078   Mean   :0.11636   Mean   :0.01362   Mean   :0.03172   Mean   :0.03298  
 3rd Qu.:0.08865   3rd Qu.:0.012612   3rd Qu.:0.15195   3rd Qu.:0.02581   3rd Qu.:0.04982   3rd Qu.:0.04961  
 Max.   :0.20658   Max.   :0.092582   Max.   :0.34499   Max.   :0.13319   Max.   :0.24225   Max.   :0.46658  
 NA's   :1         NA's   :1          NA's   :1         NA's   :1         NA's   :1         NA's   :1        
    Musical           Mystery           Romance            Sci-Fi           Thriller            War         
 Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000   Min.   :0.00000  
 1st Qu.:0.00000   1st Qu.:0.02532   1st Qu.:0.05363   1st Qu.:0.04082   1st Qu.:0.05840   1st Qu.:0.05307  
 Median :0.02779   Median :0.05064   Median :0.08512   Median :0.07962   Median :0.09511   Median :0.09136  
 Mean   :0.04094   Mean   :0.05633   Mean   :0.09278   Mean   :0.09234   Mean   :0.10013   Mean   :0.09648  
 3rd Qu.:0.06299   3rd Qu.:0.08280   3rd Qu.:0.12338   3rd Qu.:0.13499   3rd Qu.:0.13535   3rd Qu.:0.13476  
 Max.   :0.23905   Max.   :0.17252   Max.   :0.32757   Max.   :0.34179   Max.   :0.32695   Max.   :0.35029  
 NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1         NA's   :1        
    Western       
 Min.   :0.00000  
 1st Qu.:0.00000  
 Median :0.00000  
 Mean   :0.02236  
 3rd Qu.:0.04029  
 Max.   :0.15157  
 NA's   :1        
plot_sim(similarity, "cosine similarity matrix between user-genre and movie-genre")

selection <- as.data.frame(similarity)[c(241, 414, 477, 526, 640, 710), ]
genres <- colnames(selection)
selection$users <- rownames(selection)
selection_long <- selection %>% pivot_longer(cols = genres)
Note: Using an external vector in selections is ambiguous.
ℹ Use `all_of(genres)` instead of `genres` to silence this message.
ℹ See <https://tidyselect.r-lib.org/reference/faq-external-vector.html>.
This message is displayed once per session.
ggplot(selection_long, aes(x=value, fill=users)) + geom_density(alpha=0.3) + 
    labs(title="Density plot Cosinus-Ähnlichkeiten ausgewählte users", subtitle="", x="similarity")

    
#plot_sim(selection, "cosine similarity user-genre and movie-genre selection")

Empfehlbare Filme

1. Bewertete Filme maskieren, d.h. “Negativabzug” der User-Items Matrix erzeugen, um anschliessend Empfehlungen herzuleiten.

movies_masked <- movies_wider
movies_masked[-1][movies_masked[-1] == 1] <- 0
movies_masked[is.na(movies_masked)] <- 1
movies_masked

2. Zeilensumme des “Negativabzuges” der User-Items Matrix für die User “5”, “25”, “50” und “150” ausgeben.

defined_user <- c(5, 25, 50, 150)
defined_user
[1]   5  25  50 150
rowSums(movies_masked[defined_user, -1])
[1] 1489 1586 1640 1633

Hier zu sehen sind die anzahl nicht bewerteter filme pro user

3. 5-Zahlen Statistik der Zeilensumme des “Negativabzuges” der User-Items Matrix bestimmen.

rowsums_masked <- rowSums(movies_masked[, -1])
summary(rowsums_masked)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
    928    1516    1599    1558    1631    1645 

Top-N Empfehlungen

1.Matrix für Bewertung aller Filme durch element-weise Multiplikation der Matrix der Cosinus-Ähnlichkeiten von Nutzern und Filmen und “Negativabzug” der User-Items Matrix erzeugen.

rating_matrix <- user_movie_matrix * movies_masked

2.Dimension der Matrix für die Bewertung aller Filme prüfen.

dim(rating_matrix)
[1]  943 1664
rating_matrix

3.Top-20 Listen pro Nutzer extrahieren.

get_topn_recos <- function(rating_matrix, n){
  herdöpfel <- as(rating_matrix, 'realRatingMatrix')
  herdöpfel <- as(herdöpfel, 'data.frame')
  herdöpfel <- arrange(desc(herdöpfel$ratings)) %>%
    group_by(user) %>%
    slice(head(n)) %>%
    ungroup()
  return(herdöpfel)
}

recommendation <- get_topn_recos(rating_matrix, 20)
Fehler in validObject(.Object) : 
  invalid class “dgTMatrix” object: Alle Spaltenindizes (slot 'j') müssen in TsparseMatrix zwischen 0 und ncol-1 liegen

4.Länge der Top-20 Listen pro Nutzer prüfen.

summary(recommendation)
Fehler in h(simpleError(msg, call)) : 
  Fehler bei der Auswertung des Argumentes 'object' bei der Methodenauswahl für Funktion 'summary': Objekt 'recommendation' nicht gefunden

##5.Verteilung der minimalen Ähnlichkeit für Top-N Listen für N = 10, 20, 50 und 100 für alle Nutzer visuell vergleichen.

analyze_topn_recos <- function(rating_matrix, list){
  recoms <- c()
  for (n in list) {
    recoms <- append(recoms, get_topn_recos(rating_matrix, n))
  }
  return(recoms)
}

analyze_topn_recos(rating_matrix, c(10, 20, 50, 100))
Fehler in validObject(.Object) : 
  invalid class “dgTMatrix” object: Alle Spaltenindizes (slot 'j') müssen in TsparseMatrix zwischen 0 und ncol-1 liegen

TODO: igewie visualisiere

##6.Top-20 Empfehlungen für Nutzer “5”, “25”, “50” und “150” visuell evaluieren.

defined_user_lists <- get_topn_recos(ratingmatrix, 20) %>%
  filter(user == c(5, 25, 50, 50, 150)) %>%
  ungroup()
Fehler in .class1(object) : Objekt 'ratingmatrix' nicht gefunden

TODO: clevelandplot

##7.Für Nutzer “133” und “555” Profil mit Top-N Empfehlungen für N = 20, 30, 40, 50 analysieren, visualisieren und diskutieren.

analyze_topn_recos(rating_matrix[c(133, 555),], c(20, 30, 40, 50))
Fehler in validObject(.Object) : 
  invalid class “dgTMatrix” object: alle Zeilenindizes (slot 'i') müssen in TsparseMatrix zwischen 0 und nrow-1 liegen

TODO: Clevelandplot + diskussion

LS0tCnRpdGxlOiAiQ29udGVudC1iYXNlZCBSZWNvbW1lbmRlciIKYXV0aG9yOiAiUGFzY2FsIEJlcmdlciwgTGVhIELDvHRsZXIgJiBKb8OrbCBHcm9zamVhbiIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQKLS0tClItVmVyc2lvbjogKipbRGVmYXVsdF0gWzMyLWJpdF0gQzpcXFByb2dyYW0gRmlsZXNcXFJcXFItNC4xLjAqKgoKSW4gZm9sZ2VuZGVtIE5vdGVib29rIHdlcmRlbiBhbmhhbmQgZGVzIGBNb3ZpZUxlbnNlYCBEYXRlbnNhdHplcyBhdXMgZGVtIFBha2V0IFJlY29tbWVuZGVyTGFiIHZlcnNjaGllZGVuZSBSZWNvbW1lbmRlciBlcnN0ZWxsdC4gRXMgd2VyZGVuIHZlcnNjaGllZGVuZSBSZWNvbW1lbmRlciB1bmQgdmVyc2NoaWVkZW5lIMOEaG5saWNoa2VpdGVuIHZlcndlbmRldCwgdW0gZGllc2UgenUgdmVyZ2xlaWNoZW4gdW5kIGF1c3p1d2VydGVuLiBaaWVsIGlzdCBlcywgZWluIG3DtmdsaWNoc3QgZ3V0ZXIgUmVjb21tZW5kZXIgenUgZXJzdGVsbGVuIHVuZCB6dSB2ZXJzdGVoZW4gd2llIGRpZXNlciBmdW5rdGlvbmllcnQuIFp1ZGVtIHNvbGwgdmVyc3RhbmRlbiB3ZXJkZW4gd2llIGRpZXNlciBiZXdlcnRldCB3aXJkIHVuZCB3YXMgaW4gZGllc2VtIEZhbGxlIGVpbiAnZ3V0ZXInIFJlY29tbWVuZGVyIGJlZGV1dGV0LgoKRGllc2VzIE5vdGVib29rIGtvbnplbnRyaWVydCBzaWNoIGF1ZiBFcmtlbm50bmlzc2Ugdm9uIEF1c3dlcnR1bmdlbiB1bmQgVmVyZ2xlaWNoZW4uIFVtIGVpbmUgYmVzc2VyZSDDnGJlcnNpY2h0IHp1IGVyaGFsdGVuIHd1cmRlbiBncm9zc2UsIHNpY2ggd2lkZXJob2xlbmRlIENvZGVzIGltIEhlbHBlcmZpbGUgYGhlbHBlci5SYCBhdXNnZWxhZ2VydC4KCmBgYHtyIGVjaG89RkFMU0UsIGNhY2hlPUZBTFNFLCByZXN1bHRzPUZBTFNFLCBjb21tZW50PUZBTFNFLCB3YXJuaW5nPUZBTFNFfQojIG7DtnRpZ2UgUGFja2V0ZQpwYWNrYWdlcyA8LSBjKCJ0aWR5dmVyc2UiLCAiZGF0YS50YWJsZSIsICJsdWJyaWRhdGUiLCAiZ2dwbG90MiIsICJnZ3RoZW1lcyIsICJyZWNvbW1lbmRlcmxhYiIsICJrbml0ciIsICdwYWxzJywgJ1JDb2xvckJyZXdlcicsICdsYXR0aWNlJywgJ2dyaWQnLCAnZ3JpZEV4dHJhJykKCiMgTm9jaCBuaWNodCBpbnN0YWxsaWVydGUgUGFrZXRlIGluc3RhbGxpZXJlbgppbnN0YWxsZWRfcGFja2FnZXMgPC0gcGFja2FnZXMgJWluJSByb3duYW1lcyhpbnN0YWxsZWQucGFja2FnZXMoKSkKCmlmIChhbnkoaW5zdGFsbGVkX3BhY2thZ2VzID09IEZBTFNFKSkgewogIGluc3RhbGwucGFja2FnZXMocGFja2FnZXNbIWluc3RhbGxlZF9wYWNrYWdlc10pCn0KCiMgTGFkZW4gZGVyIFBhY2tldGUKaW52aXNpYmxlKGxhcHBseShwYWNrYWdlcywgbGlicmFyeSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKSkKCiMgSW1wb3J0aWVyZW4gdm9uIEZ1bmt0aW9uZW5lIGF1cyBoZWxwZXIgZmlsZQpzb3VyY2UoImhlbHBlci5SIikKCiMgY2hhbmdlIG9wdGlvbnMKb3B0aW9ucyhkcGx5ci5zdW1tYXJpc2UuaW5mb3JtID0gRkFMU0UpCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSBkYXRhIHdyYW5nbGluZyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiMgRGF0ZW4gaW1wb3J0aWVyZW4KZGF0YShNb3ZpZUxlbnNlKQoKIyBkYXRhZnJhbWUgZXJzdGVsbGVuCm1vdmllcyA8LSBhcyhNb3ZpZUxlbnNlLCAiZGF0YS5mcmFtZSIpCm1vdmllcyA8LSBtb3ZpZXMgJT4lIG11dGF0ZV9pZihpcy5jaGFyYWN0ZXIsIGFzLmZhY3RvcikKCiMgYnJlaXRlIHZlcnNpb24gZGVzIGRhdGFmcmFtZSBlcnN0ZWxsZW4KIyBtb3ZpZXNfd2lkZXIgPC0gcGl2b3Rfd2lkZXIoCiMgICBtb3ZpZXMsCiMgICBpZF9jb2xzID0gdXNlciwKIyAgIG5hbWVzX2Zyb20gPSBpdGVtLAojICAgdmFsdWVzX2Zyb20gPSByYXRpbmcsCiMgICB2YWx1ZXNfZmlsbCA9IE5VTEwsCiMgKQpgYGAKIyMgMi5CaW7DpHJlIFVzZXItTGlrZWQtSXRlbXMgTWF0cml4IGbDvHIgYWxsZSBOdXR6ZXIgZXJ6ZXVnZW4uCmBgYHtyfQptb3ZpZXNfYmluYXJ5IDwtIG1vdmllcyAlPiUgbXV0YXRlKHJhdGluZyA9IGlmZWxzZShyYXRpbmcgPiAzLCAxLCAwKSkKbW92aWVzX3dpZGVyIDwtIHBpdm90X3dpZGVyKG1vdmllc19iaW5hcnksIGlkX2NvbHMgPSB1c2VyLCBuYW1lc19mcm9tID0gaXRlbSwgdmFsdWVzX2Zyb20gPSByYXRpbmcpCnJvd25hbWVzKG1vdmllc193aWRlcikgPC0gbW92aWVzX3dpZGVyJHVzZXIKbW92aWVzX3dpZGVyWyd1c2VyJ10gPC0gTlVMTAp1c2VyX21vdmllX21hdHJpeCA8LSBhcy5tYXRyaXgobW92aWVzX3dpZGVyKQptb3ZpZXNfd2lkZXIKYGBgCkbDvHIgZGllIEJpbsOkcmUgVXNlci1MaWtlZCBNYXRyaXggc2V0enRlbiB3aXIgZGllIEdyZW56ZSBmw7xyIGVpbiBndXRlcyBSYXRpbmcgYmVpID40LiBBbHNvIGFsbGUgRmlsbWUsIHdlbGNoZSBtaXQgZWluZW0gUmF0aW5nIHZvbiAzIG9kZXIgd2VuaWdlciBiZXdlcnRldCB3dXJkZW4sIHdlcmRlbiBhbHMgc2NobGVjaHQgYmV3ZXJ0ZXQgZGVmaW5pZXJ0IChhbHNvIDApLCB3b2JlaSBGaWxtZSBtaXQgQmV3ZXJ0dW5nZW4gdm9uIDQgb2RlciA1IGFscyBndXQgYmV3ZXJ0ZXQgZGVmaW5pZXJ0IHNpbmQgKDEpLgoKYGBge3J9CmJpbmFyeV9ub25fbmEgPC0gYXMoYmluYXJpemUoTW92aWVMZW5zZSwgbWluUmF0aW5nID0gNCksICdtYXRyaXgnKSAqIDEKYmluYXJ5X25vbl9uYVsxOjMsIDE6M10KYGBgClVtIAoKIyMgMy5EaW1lbnNpb24gZGVyIFVzZXItTGlrZWQtSXRlbXMgTWF0cml4IHByw7xmZW4gdW5kIGF1c2dlYmVuLgpgYGB7cn0KZGltKHVzZXJfbW92aWVfbWF0cml4KQpgYGAKCiMjIDQuTW92aWUtR2VucmUgTWF0cml4IGbDvHIgYWxsZSBGaWxtZSBlcnpldWdlbi4KYGBge3J9CmdlbnJlcyA8LSBNb3ZpZUxlbnNlTWV0YQpnZW5yZXMgPC0gZ2VucmVzICU+JSBzZWxlY3QoInRpdGxlIiwndW5rbm93bic6J1dlc3Rlcm4nKQpyb3duYW1lcyhnZW5yZXMpIDwtIGdlbnJlcyR0aXRsZQpnZW5yZXNbJ3RpdGxlJ10gPC0gTlVMTAptb3ZpZV9nZW5yZV9tYXRyaXggPC0gYXMubWF0cml4KGdlbnJlcykKZ2VucmVzCmBgYAoKIyMgNS5EaW1lbnNpb24gZGVyIE1vdmllLUdlbnJlIE1hdHJpeCBwcsO8ZmVuIHVuZCBhdXNnZWJlbi4KYGBge3J9CmRpbShtb3ZpZV9nZW5yZV9tYXRyaXgpCmBgYApgYGB7cn0KY2xhc3MobW92aWVfZ2VucmVfbWF0cml4KQpgYGAKYGBge3J9CnVzZXJfbW92aWVfbWF0cml4WzE6MywgMTozXQpgYGAKCmBgYHtyfQpjbGFzcyh1c2VyX21vdmllX21hdHJpeCkKYGBgCgoKIyMgNi5BbnphaGwgdW50ZXJzY2hpZWRsaWNoZXIgRmlsbXByb2ZpbGUgYmVzdGltbWVuIHVuZCB2aXN1YWxpc2llcmVuLgpgYGB7cn0KbW92aWVfZ2VucmVfcHJvZmlsZV9tYXRyaXggPC0gYXMubWF0cml4KGFwcGx5KG1vdmllX2dlbnJlX21hdHJpeCA9PSAxLCAxLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZnVuY3Rpb24oYSkgcGFzdGUwKGNvbG5hbWVzKG1vdmllX2dlbnJlX21hdHJpeClbYV0sIGNvbGxhcHNlID0gIiIpKSkKbW92aWVfZ2VucmVfcHJvZmlsZV9kZiA8LSBhcy5kYXRhLmZyYW1lKG1vdmllX2dlbnJlX3Byb2ZpbGVfbWF0cml4KQptb3ZpZV9nZW5yZV9wcm9maWxlX2RmJGl0ZW1zIDwtIHJvd25hbWVzKG1vdmllX2dlbnJlX3Byb2ZpbGVfZGYpCgojbW92aWVfZ2VucmVfcHJvZmlsZV9saXN0IDwtIGModW5pcXVlKG1vdmllX2dlbnJlX3Byb2ZpbGVfZGYkVjEpKQojbW92aWVfZ2VucmVfcHJvZmlsZV9saXN0IDwtIHN0cnNwbGl0KG1vdmllX2dlbnJlX3Byb2ZpbGVfbGlzdCwgIlxuIikKI2xlbmd0aChtb3ZpZV9nZW5yZV9wcm9maWxlX2xpc3QpCgptb3ZpZV9nZW5yZV9wcm9maWxlX2RmCmBgYApUT0RPOiBpZ2V3aWUgZGllIGVpbnplbG5lIGdlbnJlcHJvZmlsIHplbGxlLCBpbmVuIGRmIHNwZWljaGVyZSB1bmQgcGxvdHRlKGdyYWZpayB2b2RlIHNsaWRlcyB2b20gZGFuaSwgZ2xhdWIgZm9saWUgMTMpCgpJbiBkZW0gTW92aWVMZW5zZSBEYXRlbnNldCBzaW5kIGluc2dlc2FtdCAyMTYgIHZlcnNjaGllZGVuZSBHZW5yZXByb2ZpbGUgdm9uIGRlbiBGaWxtZW4gdmVydHJldGVuLiBEYXMgYmVkZWl0ZXQsIGVzIHNpbmQgMjE2IHZlcnNjaGllZGVuZSBHZW5yZWtvbWJpbmF0aW9uZW4gYXVzIGRlbiAxNiBnZWdlYmVuZW4gR2VucmVzIGVudHN0YW5kZW4uCihyIGlzY2ggc28gZW4gc2VpY2ggcGzDtnR6bGljaCBicnV1Y2hzY2ggbsO2bW0gJ2FzKGRhdGEsICdkYXRhLmZyYW1lKScgc29uZGVybiAnYXMuZGF0YS5mcmFtZShkYXRhKScgV0lFU08/Pz8/KQoKYGBge3J9Cm1vdmllX2dlbnJlX3Byb2ZpbGVfZGYgPC0gbW92aWVfZ2VucmVfcHJvZmlsZV9kZiAlPiUKICBncm91cF9ieShWMSkKbW92aWVfZ2VucmVfcHJvZmlsZV9kZgpgYGAKCmBgYHtyfQpucl9kaWZmX21vdmllcyA8LSBiaW5hcnlfbm9uX25hICUqJSBtb3ZpZV9nZW5yZV9tYXRyaXgKbnJfZGlmZl9tb3ZpZXMgPC0gYXMuZGF0YS5mcmFtZShucl9kaWZmX21vdmllcykKCm5yX2RpZmZfbW92aWVzX21lYW4gPC0gcm93bmFtZXNfdG9fY29sdW1uKG5yX2RpZmZfbW92aWVzKQoKbnJfZGlmZl9tb3ZpZXNfbWVhbiA8LSBwaXZvdF9sb25nZXIobnJfZGlmZl9tb3ZpZXNfbWVhbiwgY29scyA9ICFyb3duYW1lLCBuYW1lc190byA9ICdnZW5yZScsIHZhbHVlc190byA9ICdjb3VudCcpCm5yX2RpZmZfbW92aWVzX21lYW4gPC0gbnJfZGlmZl9tb3ZpZXNfbWVhbiAlPiUgZ3JvdXBfYnkoZ2VucmUpICU+JSBzdW1tYXJpemUoY291bnQgPSBtZWFuKGNvdW50KSkKCm5yX2RpZmZfbW92aWVzCmBgYApUT0RPOiBWaXN1YWxpc2llcnVuZyBkZXIgdmVyc2NoaWVkZW5lciBOdXR6ZXJwcm9maWxlICggc2llaGUgc2xpZGUgMTMgRGFuaWVsKQpJbiBkaWVzZXIgTWF0cml4IGlzdCB6dSBzZWhlbiB3aWUgdmllbGUgRmlsbWUgcHJvIGdlbnJlIG1pdCBtZWhyIGFscyAzIGJld2VydGV0IHd1cmRlbiwgamV3ZWlscyBwcm8gVXNlci4KYGBge3J9Cm5yX2RpZmZfbW92aWVzX21lYW4KYGBgCgpgYGB7cn0KbnJfZGlmZl9tb3ZpZXNfbWVhbiAlPiUgbXV0YXRlKGdlbnJlID0gZmN0X3Jlb3JkZXIoZ2VucmUsIGNvdW50KSkgJT4lIAogIGdncGxvdChhZXMoeCA9IGdlbnJlLCB5ID0gY291bnQpKSArIAogIGdlb21fY29sKGZpbGwgPSAnc3RlZWxibHVlJykgKwogIGNvb3JkX2ZsaXAoKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSwgbGltaXRzID0gYygwLCAzMCkpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsID0gcm91bmQoY291bnQsIDIpKSwgaGp1c3Q9LTAuMiwgY29sb3IgPSAnYmxhY2snKSArCiAgbGFicygKICAgIHRpdGxlID0gIkR1Y2hzY2huaXR0bGljaGUgQW56YWhsIHBvc2l0aXYgYmV3ZXJ0ZXRlciBGaWxtZSBwcm8gR2VucmUiLAogICAgeCA9IGVsZW1lbnRfYmxhbmsoKSwgCiAgICB5ID0gIkFuemFobCIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgdGhlbWVfY2xhc3NpYygpICsgCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgCgojIyA3LlVzZXItR2VucmUtUHJvZmlsIE1hdHJpeCBtaXQgTnV0emVycHJvZmlsZW4gaW0gR2VucmUtVmVrdG9ycmF1bSBlcnpldWdlbi4KCiMjOC5EaW1lbnNpb24gZGVyIFVzZXItR2VucmUtUHJvZmlsIE1hdHJpeCBwcsO8ZmVuIHVuZCBhdXNnZWJlbi4KCiMjIDkuQW56YWhsIHVudGVyc2NoaWVkbGljaGVyIE51dHplcnByb2ZpbGUgYmVzdGltbWVuLCB3ZW5uIFN0w6Rya2UgZGVyIEdlbnJlS29tYmluYXRpb24gKGEpIHZvbGxzdMOkbmRpZyBiencuIChiKSBudXIgYmluw6RyIGJlcsO8Y2tzaWNodGlndCB3aXJkLgoKIyMgw4RobmxpY2hrZWl0IHZvbiBOdXR6ZXJuIHVuZCBGaWxtZW4KCiMjIDEuQ29zaW51cy3DhGhubGljaGtlaXQgendpc2NoZW4gVXNlci1HZW5yZS0gdW5kIE1vdmllLUdlbnJlLU1hdHJpeCBiZXJlY2huZW4uCgojIyMgVGVzdApgYGB7cn0KCkFfdGVzdC5kYXRhIDwtIGMoMS41LDIuNSwgMS4sMC41KQpBX3Rlc3QgPC0gbWF0cml4KEFfdGVzdC5kYXRhLCBucm93PTIpCkFfdGVzdAoKQl90ZXN0LmRhdGEgPC0gYygwLjUsMS4sIDEuNSwyLikKQl90ZXN0IDwtIG1hdHJpeChCX3Rlc3QuZGF0YSwgbnJvdz0yKQpCX3Rlc3QKCnJlc3VsdCA8LSBjYWxjX2Nvc19zaW1pbGFyaXR5X3R3b210cngoQV90ZXN0LCBCX3Rlc3QpCgppZigoZGltKHJlc3VsdCkgPT0gZGltKEJfdGVzdCkpICYmIChkaW0ocmVzdWx0KSA9PSBkaW0oQV90ZXN0KSkpIHsKICBwcmludCgiZGltZW5zaW9ucyBtYXRjaCIpCn0gZWxzZSB7CiAgcHJpbnQoImRpbWVuc2lvbnMgZG8gbm90IG1hdGNoIikKfQpjaGVjay5kYXRhIDwtIGMoMC43OSwgMC41MCwgMC44NywgMC42MSkKY2hlY2sgPC0gbWF0cml4KGNoZWNrLmRhdGEsIG5yb3c9MikKCmlmKG1heChhYnMoY2hlY2sgLSByZXN1bHQpKSA8IDFlLTIpewogIHByaW50KCJjaGVjayBtYXRjaCIpCn0gZWxzZXsKICBwcmludCgiY2hlY2sgZGlmZmVycyBmcm9tIHJlc3VsdCIpCn0KCgpgYGAKCkluIGRpZXNlbSBCZWlzcGllbCB3dXJkZSBmw7xyIHp3ZWkgMngyIE1hdHJpemVuIG1pdCB6dWbDpGxsaWcgZ2V3w6RobHRlbiBXZXJ0ZW4gZGllIGNvc2luZSBzaW1pbGFyaXR5IGJlcmVjaG5ldC4gRGllc2UgQmVyZWNobnVuZyB3dXJkZSBlYmVuZmFsbHMgdm9uIEhhbmQgZ2VtYWNodCB1bmQgbWl0IGRlciBJbXBsZW1lbnRpZXJ1bmcgYWJnZWdlbGljaGVuLiBadXPDpHR6bGljaCB3dXJkZW4gZGllIERpbWVuc2lvbmVuIGRlciBJbnB1dHZhcmlhYmxlbiBtaXQgZGVyZW4gZGVzIFJlc3VsdGF0ZXMgYWJnZWdsaWNoZW4uIERpZSBCZXJlY2hudW5nIGRlciBDb3NpbmUgU2ltaWxhcml0eSBzb2xsdGUgc28ga29ycmVrdCBzZWluLgoKCkFuc2NobGllc3NlbmQgd2lyZCBkaWUgQ29zaW5lIFNpbWlsYXJpdHkgZGVyIHVzZXItZ2VucmUgdW5kIG1vdmllLWdlbnJlIE1hdHJpeGJlcmVjaG5ldC4KCmBgYHtyfQp1c2VyX21vdmllX25vbl9uYSA8LSB1c2VyX21vdmllX21hdHJpeAp1c2VyX21vdmllX25vbl9uYVtpcy5uYSh1c2VyX21vdmllX25vbl9uYSldIDwtIDAKdXNlcl9tb3ZpZV9ub25fbmFbMTo1LCAxOjVdCmBgYAoKCmBgYHtyfQoKc2ltaWxhcml0eSA8LSBjYWxjX2Nvc19zaW1pbGFyaXR5X3R3b210cngodXNlcl9tb3ZpZV9ub25fbmEsIHQobW92aWVfZ2VucmVfbWF0cml4KSkKCmBgYAoKYGBge3J9CnN1bW1hcnkoc2ltaWxhcml0eSkKYGBgCgoKYGBge3J9CnBsb3Rfc2ltKHNpbWlsYXJpdHksICJjb3NpbmUgc2ltaWxhcml0eSBtYXRyaXggYmV0d2VlbiB1c2VyLWdlbnJlIGFuZCBtb3ZpZS1nZW5yZSIpCmBgYAoKCmBgYHtyfQpzZWxlY3Rpb24gPC0gYXMuZGF0YS5mcmFtZShzaW1pbGFyaXR5KVtjKDI0MSwgNDE0LCA0NzcsIDUyNiwgNjQwLCA3MTApLCBdCmdlbnJlcyA8LSBjb2xuYW1lcyhzZWxlY3Rpb24pCnNlbGVjdGlvbiR1c2VycyA8LSByb3duYW1lcyhzZWxlY3Rpb24pCnNlbGVjdGlvbl9sb25nIDwtIHNlbGVjdGlvbiAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBnZW5yZXMpCgpnZ3Bsb3Qoc2VsZWN0aW9uX2xvbmcsIGFlcyh4PXZhbHVlLCBmaWxsPXVzZXJzKSkgKyBnZW9tX2RlbnNpdHkoYWxwaGE9MC4zKSArIAogICAgbGFicyh0aXRsZT0iRGVuc2l0eSBwbG90IENvc2ludXMtw4RobmxpY2hrZWl0ZW4gYXVzZ2V3w6RobHRlIHVzZXJzIiwgc3VidGl0bGU9IiIsIHg9InNpbWlsYXJpdHkiKQogICAgCiNwbG90X3NpbShzZWxlY3Rpb24sICJjb3NpbmUgc2ltaWxhcml0eSB1c2VyLWdlbnJlIGFuZCBtb3ZpZS1nZW5yZSBzZWxlY3Rpb24iKQoKYGBgCgojIyMgRW1wZmVobGJhcmUgRmlsbWUKIyMgMS4gQmV3ZXJ0ZXRlIEZpbG1lIG1hc2tpZXJlbiwgZC5oLiDigJxOZWdhdGl2YWJ6dWfigJ0gZGVyIFVzZXItSXRlbXMgTWF0cml4IGVyemV1Z2VuLCB1bSBhbnNjaGxpZXNzZW5kIEVtcGZlaGx1bmdlbiBoZXJ6dWxlaXRlbi4KYGBge3J9Cm1vdmllc19tYXNrZWQgPC0gbW92aWVzX3dpZGVyCm1vdmllc19tYXNrZWRbLTFdW21vdmllc19tYXNrZWRbLTFdID09IDFdIDwtIDAKbW92aWVzX21hc2tlZFtpcy5uYShtb3ZpZXNfbWFza2VkKV0gPC0gMQptb3ZpZXNfbWFza2VkCmBgYAoKIyMgMi4gWmVpbGVuc3VtbWUgZGVzIOKAnE5lZ2F0aXZhYnp1Z2Vz4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBmw7xyIGRpZSBVc2VyIOKAnDXigJ0sIOKAnDI14oCdLCDigJw1MOKAnSB1bmQg4oCcMTUw4oCdIGF1c2dlYmVuLgpgYGB7cn0KZGVmaW5lZF91c2VyIDwtIGMoNSwgMjUsIDUwLCAxNTApCmRlZmluZWRfdXNlcgpyb3dTdW1zKG1vdmllc19tYXNrZWRbZGVmaW5lZF91c2VyLCAtMV0pCmBgYApIaWVyIHp1IHNlaGVuIHNpbmQgZGllIGFuemFobCBuaWNodCBiZXdlcnRldGVyIGZpbG1lIHBybyB1c2VyCgojIyAzLiA1LVphaGxlbiBTdGF0aXN0aWsgZGVyIFplaWxlbnN1bW1lIGRlcyDigJxOZWdhdGl2YWJ6dWdlc+KAnSBkZXIgVXNlci1JdGVtcyBNYXRyaXggYmVzdGltbWVuLgpgYGB7cn0Kcm93c3Vtc19tYXNrZWQgPC0gcm93U3Vtcyhtb3ZpZXNfbWFza2VkWywgLTFdKQpzdW1tYXJ5KHJvd3N1bXNfbWFza2VkKQpgYGAKCiMjIFRvcC1OIEVtcGZlaGx1bmdlbgojIyAxLk1hdHJpeCBmw7xyIEJld2VydHVuZyBhbGxlciBGaWxtZSBkdXJjaCBlbGVtZW50LXdlaXNlIE11bHRpcGxpa2F0aW9uIGRlciBNYXRyaXggZGVyIENvc2ludXMtw4RobmxpY2hrZWl0ZW4gdm9uIE51dHplcm4gdW5kIEZpbG1lbiB1bmQg4oCcTmVnYXRpdmFienVn4oCdIGRlciBVc2VyLUl0ZW1zIE1hdHJpeCBlcnpldWdlbi4KYGBge3J9CnJhdGluZ19tYXRyaXggPC0gdXNlcl9tb3ZpZV9tYXRyaXggKiBtb3ZpZXNfbWFza2VkCmBgYAoKIyMgMi5EaW1lbnNpb24gZGVyIE1hdHJpeCBmw7xyIGRpZSBCZXdlcnR1bmcgYWxsZXIgRmlsbWUgcHLDvGZlbi4KYGBge3J9CmRpbShyYXRpbmdfbWF0cml4KQpgYGAKCmBgYHtyfQpyYXRpbmdfbWF0cml4CmBgYAoKCiMjIDMuVG9wLTIwIExpc3RlbiBwcm8gTnV0emVyIGV4dHJhaGllcmVuLgpgYGB7cn0KZ2V0X3RvcG5fcmVjb3MgPC0gZnVuY3Rpb24ocmF0aW5nX21hdHJpeCwgbil7CiAgaGVyZMO2cGZlbCA8LSBhcyhyYXRpbmdfbWF0cml4LCAncmVhbFJhdGluZ01hdHJpeCcpCiAgaGVyZMO2cGZlbCA8LSBhcyhoZXJkw7ZwZmVsLCAnZGF0YS5mcmFtZScpCiAgaGVyZMO2cGZlbCA8LSBhcnJhbmdlKGRlc2MoaGVyZMO2cGZlbCRyYXRpbmdzKSkgJT4lCiAgICBncm91cF9ieSh1c2VyKSAlPiUKICAgIHNsaWNlKGhlYWQobikpICU+JQogICAgdW5ncm91cCgpCiAgcmV0dXJuKGhlcmTDtnBmZWwpCn0KCnJlY29tbWVuZGF0aW9uIDwtIGdldF90b3BuX3JlY29zKHJhdGluZ19tYXRyaXgsIDIwKQpyZWNvbW1lbmRhdGlvbgpgYGAKCiMjIDQuTMOkbmdlIGRlciBUb3AtMjAgTGlzdGVuIHBybyBOdXR6ZXIgcHLDvGZlbi4KYGBge3J9CnN1bW1hcnkocmVjb21tZW5kYXRpb24pCmBgYAoKIyM1LlZlcnRlaWx1bmcgZGVyIG1pbmltYWxlbiDDhGhubGljaGtlaXQgZsO8ciBUb3AtTiBMaXN0ZW4gZsO8ciBOID0gMTAsIDIwLCA1MCB1bmQgMTAwIGbDvHIgYWxsZSBOdXR6ZXIgdmlzdWVsbCB2ZXJnbGVpY2hlbi4KYGBge3J9CmFuYWx5emVfdG9wbl9yZWNvcyA8LSBmdW5jdGlvbihyYXRpbmdfbWF0cml4LCBsaXN0KXsKICByZWNvbXMgPC0gYygpCiAgZm9yIChuIGluIGxpc3QpIHsKICAgIHJlY29tcyA8LSBhcHBlbmQocmVjb21zLCBnZXRfdG9wbl9yZWNvcyhyYXRpbmdfbWF0cml4LCBuKSkKICB9CiAgcmV0dXJuKHJlY29tcykKfQoKYW5hbHl6ZV90b3BuX3JlY29zKHJhdGluZ19tYXRyaXgsIGMoMTAsIDIwLCA1MCwgMTAwKSkKYGBgClRPRE86IGlnZXdpZSB2aXN1YWxpc2llcmUKCiMjNi5Ub3AtMjAgRW1wZmVobHVuZ2VuIGbDvHIgTnV0emVyIOKAnDXigJ0sIOKAnDI14oCdLCDigJw1MOKAnSB1bmQg4oCcMTUw4oCdIHZpc3VlbGwgZXZhbHVpZXJlbi4KYGBge3J9CmRlZmluZWRfdXNlcl9saXN0cyA8LSBnZXRfdG9wbl9yZWNvcyhyYXRpbmdtYXRyaXgsIDIwKSAlPiUKICBmaWx0ZXIodXNlciA9PSBjKDUsIDI1LCA1MCwgNTAsIDE1MCkpICU+JQogIHVuZ3JvdXAoKQoKZGVmaW5lZF91c2VyX2xpc3RzCmBgYApUT0RPOiBjbGV2ZWxhbmRwbG90CgojIzcuRsO8ciBOdXR6ZXIg4oCcMTMz4oCdIHVuZCDigJw1NTXigJ0gUHJvZmlsIG1pdCBUb3AtTiBFbXBmZWhsdW5nZW4gZsO8ciBOID0gMjAsIDMwLCA0MCwgNTAgYW5hbHlzaWVyZW4sIHZpc3VhbGlzaWVyZW4gdW5kIGRpc2t1dGllcmVuLgpgYGB7cn0KYW5hbHl6ZV90b3BuX3JlY29zKHJhdGluZ19tYXRyaXhbYygxMzMsIDU1NSksXSwgYygyMCwgMzAsIDQwLCA1MCkpCmBgYApUT0RPOiBDbGV2ZWxhbmRwbG90ICsgZGlza3Vzc2lvbgo=